% Ejercicio "Algoritmo de Earley"
\subsection*{\fbox{\theejercicio} - Algoritmo de Earley}

Las t\'ecnicas de an\'alisis sint\'actico que hemos estudiado est\'an limitadas a un subconjunto propio de las gram\'aticas de contexto libre. Ocasionalmente, puede ser necesario utilizar analizadores sint\'acticos que sirvan para cualquier gram\'atica de contexto libre, ambigua o no. Uno de los m\'etodos mas conocidos para llevar a cabo esta tarea es el algoritmo atribuido a Jay Earley (1970). Este algoritmo puede considerarse como una versi\'on interpretada de la t\'ecnica de an\'alisis LR(0).

\smallskip

A diferencia de los metodos LR, el algoritmo de Earley no utiliza tokens de lectura avanzada para decidir cua
debe ser la proxima acci\'on a realizar. En caso de existir un conflicto entre una reducci\'on y un desplazamiento, o entre
dos reducciones, el algoritmo de Earley lanza todas las posibles acciones en paralelo. Por tanto, no es necesario halla
previamente una tabla de an\'alisis, como se hace en los an\'alisis LR. La colecci\'on de conjuntos de items se va calculando
simultaneamente al reconocimiento de la cadena a analizar.

\smallskip

En el algoritmo de Earley, los items LR(0), se aumentan con una segunda componente, un valor entero al que
lamaremos puntero de predicci\'on. El puntero de predicci\'on representa el conjunto de items a partir del cual se obtuvo
el nuevo conjunto de items. Este puntero es necesario, para poder tratar gram\'aticas ambiguas, en las que un item LR(0)
puede ser generado mas de una vez en un mismo estado o conjunto de items, representando varias estructuras
sint\'acticas diferentes. Los conjuntos de items se manipulan de una forma similar a la colecci\'on de items LR(0), con las
siguientes reglas:

\begin{enumerate}
\item El estado inicial se obtiene a partir del item LR(0) aumentado $[S'\rightarrow\cdot S\$,0]$, calculando su cierre mediante la regla 2.

\item Si el estado $i$ (conjunto de items $i$) contiene un item de la forma $[A\rightarrow \alpha\cdot B\beta,j]$ entonces el estado $i$ debe contener tambi\'en un item de la forma $[B\rightarrow\cdot\gamma,i]$, para toda regla $B\rightarrow\gamma$ de la gram\'atica.

\item Si el estado $i$ contiene uno o m\'as items de la forma $[A\rightarrow\alpha\cdot X\beta,j]$ y el siguiente s\'{\i}mbolo en la entrada es precisamente X, entonces se crea un nuevo estado $i+1$, en el que se incluyen los correspondientes items $[A\rightarrow\alpha X\cdot\beta,j]$, calculando su cierre mediante las reglas 2 y 4, y avanzando la cabeza de lectura.

\item Si el estado $i$ contiene un item completo, de la forma $[A\rightarrow\gamma\cdot,j]$, sabemos que el item que di\'o origen a \'este fu\'e creado en el estado $j$, por tanto, buscaremos en el estado $j$ todos los items de la forma $[B\rightarrow\alpha\cdot A\beta,k]$, y a\~nadiremos al estado $i$ los correspondientes items de la forma $[B\rightarrow\alpha A\cdot\beta,k]$. Esta operaci\'on equivale a una reducci\'on en la pila de an\'alisis en la que se ha encontrado el consecuente de la regla, ($\gamma$), se ha sustituido por el antecedente, ({\em A}), y se ha realizado un desplazamiento sobre \'el.

\item Tras una entrada compuesta por $n$ tokens, habremos obtenido $n+1$ estados o conjuntos de items. Si el \'ultimo estado contiene el item de la forma $[S'\rightarrow S\$\cdot,0]$, podremos asegurar que la cadena de tokens de la entrada es sint\'acticamente correcta.

\smallskip

En la pr\'actica, el algoritmo de Earley es muy ineficiente desde el punto de vista computacional, pero puede tener inter\'es en sistemas experimentales. En general las aplicaciones que requieran gram\'aticas ambiguas o sin ning\'un tipo de restricci\'on deben usar m\'etodos de an\'alisis como el algoritmo de Earley. Las \'areas de aplicaci\'on de este algoritmo son, por tanto: el procesamiento de lenguaje natural, la generaci\'on autom\'atica de c\'odigo y el desarrolo de lenguajes con gram\'aticas extensibles por el usuario.
\end{enumerate}

Ejemplo: Sea la gram\'atica aumentada

\begin{center}
\begin{tabular}{|lcl|} \hline
        &               &                   \\
{\em S} & $\rightarrow$ & {\em E} {\bf \$}  \\
{\em E} & $\rightarrow$ & {\em E} + {\em E} \\
{\em E} & $\rightarrow$ & {\bf a}           \\
        &               &                   \\ \hline
\end{tabular}
\end{center}

El an\'alisis sintat\'actico de la cadena \verb@a+a+a$@ siguiendo el algoritmo de Earley construye los siguientes estados:

\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
\underline{Estado 0}         & \underline{Estado 1}        & \underline{Estado 2}         & \underline{Estado 3}        \\
                             &                             &                              &                             \\
$[S\rightarrow\cdot E\$,0]$  & $[E\rightarrow a\cdot,0]$   & $[E\rightarrow E+\cdot E,0]$ & $[E\rightarrow a\cdot,2]$   \\
$[E\rightarrow\cdot E+E,0]$  & $[S\rightarrow E\cdot\$,0]$ & $[E\rightarrow\cdot E+E,2]$  & $[E\rightarrow E+E\cdot,0]$ \\
$[E\rightarrow\cdot a,0]$    & $[E\rightarrow E\cdot+E,0]$ & $[E\rightarrow\cdot a,2]$    & $[E\rightarrow E\cdot+E,2]$ \\
                             &                             &                              & $[E\rightarrow E\cdot+E,0]$ \\
                             &                             &                              & $[S\rightarrow E\cdot\$,0]$ \\ \hline
\underline{Estado 4}         & \underline{Estado 5}        & \underline{Estado 6}         &                             \\
                             &                             &                              &                             \\
$[E\rightarrow E+\cdot E,2]$ & $[E\rightarrow a\cdot,4]$   & $[S\rightarrow E\$\cdot,0]$  &                             \\
$[E\rightarrow E+\cdot E,0]$ & $[E\rightarrow E+E\cdot,2]$ &                              &                             \\
$[E\rightarrow\cdot E+E,4]$  & $[E\rightarrow E+E\cdot,0]$ &                              &                             \\
$[E\rightarrow\cdot a,4]$    & $[E\rightarrow E\cdot+E,4]$ &                              &                             \\
                             & $[E\rightarrow E\cdot+E,2]$ &                              &                             \\
                             & $[S\rightarrow E\cdot\$,0]$ &                              &                             \\
                             & $[E\rightarrow E\cdot+E,0]$ &                              &                             \\ \hline
\end{tabular}
\end{center}

\begin{enumerate}[1)]
\item Hallar los estados que el algoritmo de Earley construye al analizar la cadena de entrada \verb@"ababa$"@, usando la gram\'atica aumentada:

\begin{center}
\begin{tabular}{|lcl|} \hline
        &               &                       \\
{\em S} & $\rightarrow$ & {\em A}{\bf \$}       \\
{\em A} & $\rightarrow$ & {\bf a}{\em B}{\bf a} \\
{\em A} & $\rightarrow$ & {\bf a}               \\
{\em B} & $\rightarrow$ & {\bf b}{\em A}{\bf b} \\
{\em B} & $\rightarrow$ & {\bf b}               \\
        &               &                       \\ \hline
\end{tabular}
\end{center}

\item Como puede comprobarse, la gram\'atica propuesta no es ambigua, pero al construir cualquier tabla de acciones de la familia LR(1), aparecen conflictos. Sin embargo, es posible hallar una gram\'atica equivalente analizable f\'acilmente mediante las t\'ecnicas habituales. Hallar esta gram\'atica y construir las tablas de an\'alisis SLR(1) correspondientes.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

\medskip

Los estados del algoritmo de Earley corresponden a los conjuntos de items:

\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
\underline{Estado 0}          & \underline{Estado 1}         & \underline{Estado 2}         & \underline{Estado 3}         \\
                              &                              &                              &                              \\
$[S\rightarrow\cdot A\$,0]$   & $[A\rightarrow a\cdot Ba,0]$ & $[B\rightarrow b\cdot Ab,1]$ & $[A\rightarrow a\cdot Ba,2]$ \\
$[A\rightarrow\cdot aBa,0]$   & $[A\rightarrow a\cdot\$,0]$  & $[B\rightarrow b\cdot,1]$    & $[A\rightarrow a\cdot,2]$    \\
$[A\rightarrow\cdot a,0]$     & $[B\rightarrow \cdot bAb,1]$ & $[A\rightarrow \cdot aBa,2]$ & $[A\rightarrow aBa\cdot,0]$  \\
                              & $[B\rightarrow \cdot b,1]$   & $[A\rightarrow \cdot a,2]$   & $[B\rightarrow \cdot bAb,3]$ \\
                              & $[S\rightarrow A\cdot\$,0]$  & $[A\rightarrow aB\cdot a,0]$ & $[B\rightarrow \cdot b,3]$   \\
                              &                              &                              & $[B\rightarrow bA\cdot b,1]$ \\
                              &                              &                              & $[B\rightarrow A\cdot\$,0]$  \\
\underline{Estado 4}          & \underline{Estado 5}         & \underline{Estado 6}         &                              \\
                              &                              &                              &                              \\
$[B\rightarrow b\cdot Ab,3]$  & $[A\rightarrow a\cdot Ba,4]$ & $[S\rightarrow A\$\cdot,0]$  &                              \\
$[B\rightarrow b\cdot,3]$     & $[A\rightarrow a\cdot,4]$  &                              &                                \\
$[B\rightarrow bAb\cdot,1]$   & $[A\rightarrow aBa\cdot,2]$  &                              &                              \\
$[A\rightarrow\cdot aBa a,4]$ & $[A\rightarrow aBa\cdot,0]$  &                              &                              \\
$[A\rightarrow\cdot a,4]$     & $[B\rightarrow \cdot bAb,5]$ &                              &                              \\
$[A\rightarrow aB\cdot a,2]$  & $[B\rightarrow \cdot b,5]$   &                              &                              \\
$[A\rightarrow aB\cdot a,0]$  & $[B\rightarrow bA\cdot b,3]$ &                              &                              \\
                              & $[B\rightarrow bA\cdot b,1]$ &                              &                              \\
                              & $[S\rightarrow A\cdot\$,0]$  &                              &                              \\ \hline
\end{tabular}
\end{center}

Apartado 2)

\medskip

Una gram\'atica equivalente a la propuesta es:

\begin{center}
\begin{tabular}{|llcl|} \hline
        &         &               &                 \\
{\tt 1} & {\em S} & $\rightarrow$ & {\em A}{\bf \$} \\
{\tt 2} & {\em A} & $\rightarrow$ & {\em A}{\bf ba} \\
{\tt 3} & {\em A} & $\rightarrow$ & {\bf a}         \\
        &         &               &                 \\ \hline
\end{tabular}
\end{center}

cuya tablas de an\'alisis son:

\begin{center}
\begin{tabular}{|l|ccccc|} \hline
        & {\bf a} & {\bf b} & {\bf \$} & {\em A} & {\em S} \\ \hline
{\tt 0} & D1      &         &          & 2       &         \\
{\tt 1} &         & $R_3$   & $R_3$    &         &         \\
{\tt 2} &         & D4      & D3       &         &         \\
{\tt 3} &         &         & A        &         &         \\
{\tt 4} & D5      &         &          &         &         \\
{\tt 5} &         & $R_2$   & $R_2$    &         &         \\ \hline
\end{tabular}
\end{center}